The growth in use of portable pen-based computing devices, such as PDAs, has resulted in an increased desire to process the input ‘stroke’ data in time and data-storage efficient manner. Prior art techniques involve translating the input stroke data, which is input via means of a stylus tracing out a character on a suitable touchscreen, into computer-readable, or ASCII, text.
In this way, if a user enters handwritten data, it is generally stored in the form of plain ASCII text in the device's data store. Then, if the user wishes to perform a search for a word amongst that data, he must enter the handwritten word, which is again translated, using character recognition techniques, into plain ASCII text to enable the computer to locate the stored word, which is then displayed in a computer-generated typeface or font.
Increasingly, it is felt that the step of translating handwritten data entries into ASCII text is an unnecessary step. However, it is presently the most efficient way to store large amounts of data. This is because the storage of handwritten data as image files is prohibitively memory intensive. Even storing the strokes as a series of x-y co-ordinates can consume large amounts of memory.
Generally, digital ink is structured as a sequence of strokes that begin when the pen device makes contact with a drawing surface and ends when the pen device is lifted. Each stroke comprises a set of sampled coordinates that define the movement of the pen whilst the pen is in contact with the drawing surface.
As stated, the increasing use of pen computing and the emergence of paper-based interfaces to networked computing resources has highlighted the need for techniques to compress digital ink. This is illustrated in a press release by Anoto: “Anoto, Ericsson, and Time Manager Take Pen and Paper into the Digital Age with the Anoto Technology”, 6 Apr., 2000. Since written ink is a more expressive and flexible format than text, it is desirable that pen-computing systems support the storage, retrieval, and reproduction of raw digital ink. However, since digital ink representations of information are often far larger than their corresponding traditional representation (e.g. the digital ink representing handwriting is far larger than the corresponding ASCII text), digital ink compression is needed to ensure efficient transmission and storage of this data type.
In the field of telephony, delta encoding is a known technique for the compression of telephone-quality speech signals. Differential Pulse Code Modulation (DPCM) exploits the fact that most of the energy in a speech signal occurs at low frequencies, and thus given a sufficiently high sample rate the difference between successive samples is generally smaller than the magnitude of the samples themselves. A more sophisticated compression scheme, Adaptive Differential Pulse Code Modulation (ADPCM) is used to compress 64 Kb/s speech signals to a number of bit rates down to 16 Kb/s. This technique, defined in ITU standard 0.726 (International Telecommunication Union (ITU), “40, 32, 24, 16 Kbit/s Adaptive Differential Pulse Code Modulation (ADPCM)”, ITU-T Recommendation G.726) adapts the magnitude of the delta step size based on a statistical analysis of a short-term frame of the speech signal.
Similarly, linear predictive coding (LPC) has been used to compress telephone-quality speech to very low bit-rates. Generally, LPC audio compression is lossy and introduces significant distortion, an example being the LPC-10e standard that produces poor-quality, synthetic sounding compressed speech at 2.4 Kb/s. More sophisticated compression schemes based on LPC have been developed that produce much higher quality signals at correspondingly higher bit rates (e.g. the Code-Excited Linear Prediction (CELP) compression scheme described in ITU standard G.723.1 (International Telecommunication Union (ITU), “Dual Rate Speech Coder for Multimedia Telecommunication Transmitting at 5.3 and 6.3 Kbit/s”, ITU-T Recommendation G.723.1).
U.S. Pat. No. 6,212,295 describes a procedure for the reconstruction of handwritten dynamics by “accumulating increments of values that are some function of the original data”. The technique uses a non-linear function to accentuate the velocity component of the original signal for use in a handwritten signature verification system.
A number of commercial vendors have developed products that perform lossy digital ink compression. Communications Intelligence Corporation offer a product called INKShrINK that “stores high resolution electronic ink for far less than a compressed image”. The product offers six levels of optimization that offer a trade off between size and reconstructed image quality. Another ink compression scheme based on approximation using Bezier curves is described in the JOT standard: Slate Corporation, “JOT—A Specification for an Ink Storage and Interchange Format”, May 1993.
These prior art documents indicate that an efficient and straightforward compression scheme is required in order to capitalise on the potential offered by digital ink. The present invention aims to address this problem.